package com.togo.algorithm.easy.link;


import com.togo.algorithm.common.ListNode;
import com.togo.algorithm.util.ArrayUtil;
import com.togo.algorithm.util.ListNodeUtil;

/**
 * <p>
 * Class : com.togo.algorithm.easy.MergeTwoSortedLists
 * <p>
 * Descdription:将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 * <p>
 * 示例：
 * <p>
 * 输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
 *
 * @author taiyn
 * @version 1.0.0
 * <p>
 * --------------------------------------------------------------<br>
 * 修改履历：<br>
 * <li>2019年3月21日，taiyn，创建文件；<br>
 * --------------------------------------------------------------<br>
 * </p>
 */
class MergeTwoSortedLists21 {

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        if (l1 == null)
            return l2;
        if (l2 == null)
            return l1;

        ListNode newHead = new ListNode(0);
        ListNode current = newHead;

        while (l1 != null && l2 != null) {

            if (l1.val <= l2.val) {
                current.next = l1;
                l1 = l1.next;
                current = current.next;
            } else {
                current.next = l2;
                l2 = l2.next;
                current = current.next;
            }
        }

        if (l1 != null) {
            current.next = l1;
        }
        if (l2 != null) {
            current.next = l2;
        }

        return newHead.next;
    }

    public ListNode mergeTwoListsByRecursive(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;

        if (list1.val < list2.val) {
            list1.next = mergeTwoListsByRecursive(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoListsByRecursive(list1, list2.next);
            return list2;
        }
    }

    public static void main(String[] args) {

        int[] array1 = new int[]{1, 2, 4};
        int[] array2 = new int[]{1, 3, 4};
        ListNode list1 = ListNodeUtil.buildByArray(array1);
        ListNode list2 = ListNodeUtil.buildByArray(array2);

        MergeTwoSortedLists21 mergeTwoSortedLists21 = new MergeTwoSortedLists21();
        ListNode node = mergeTwoSortedLists21.mergeTwoListsByRecursive(list1, list2);

        ListNodeUtil.print(node);
    }
}
